<?php
header("content-type:text/html;charset=utf-8");

$arr = array(10,33,1,2,3,2,5,7,8,12);
echo "原来数组：";
echo implode(" ", $arr)."<br/>";

/**
 * 冒泡排序
 */
/**
 * 算法原理
 * 冒泡排序算法的运作如下：
 * 1.从后往前
 * 2.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 * 3.对每一对相邻的元素作同样的工作，从开始第一对到结尾的最后一对。
 * 4.针对所有的元素重复以上的步骤，除了最后一个。
 * 5.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 */
function BubbleSort($arr) {
	//获取数组的长度
	$lenght = count($arr);
	//数组只有一位，就不需要排序
	if ($lenght<=1) {
		return $arr;
	}
	//根据数组的长度来判断要循环多少次
	for ($i=0; $i < $lenght; $i++) { 
		// 除了最后一个
		// j 的位置大于 i 的位置，就一直递减
		for ($j=$lenght-1; $j > $i; $j--) { 
			// 如果最后一位小于前一位
			if ($arr[$j] <$arr[$j-1]) {
				//取最后一位的值存到 tmp里面
				$tmp = $arr[$j];
				//前一位赋值给最后一位
				$arr[$j]=$arr[$j-1];
				//最后一位赋值给前一位
				$arr[$j-1] = $tmp;
				//这样就实现了两位数的相互交换，也就是小的放前面，大的放后面
			}
		}
	}
	return $arr;
}

echo '冒泡排序：';
echo implode(' ', BubbleSort($arr))."<br/>";


/**
 * 快速排序
 */
/**
 * 算法介绍：
 * 设要排序的数组是A[0]....A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。
 * 
 * 一趟快速排序的算法是：
 * 1.设置两个变量i、j，排序开始的时候：i=0,j=N-1
 * 2.以第一个数组元素作为关键数据，赋值给key，即key=A[0]
 * 3.从j开始从前搜索，即由后开始向前搜索（j--），找到第一个小于key的值A[j]，将A[j]和A[i]
 * 4.从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于key的A[i]，将A[i]和A[j]互换
 * 5.重复3、4步，直到i=j
 */
function QSort($arr){
	$lenght = count($arr);
	if($lenght<=1){
		return $arr;
	}
	$pivot = $arr[0]; //枢轴,key的值，也就是取数组的第一个
	$left_arr = array();
	$right_arr = array();
	//i从1开始，0是枢轴
	for($i=1;$i<$lenght;$i++){
		//如果往后的数小于A[0]，将这个数给 $left_arr[]
		//否则给 $right_arr[]
		if($arr[$i]<=$pivot){
			$left_arr[]=$arr[$i];
		} else{
			$right_arr[]=$arr[$i];
		}
	}
	//再对选出来的值进行递归处理
	$left_arr = QSort($left_arr);//递归排序左半部分
	$right_arr = QSort($right_arr);//递归排序右半部分
	//进行数组的合并
	return array_merge($left_arr,array($pivot),$right_arr);
}
echo "快速排序：";
echo implode(' ', QSort($arr))."<br/>";


/**
 * 插入排序
 * 直接插入排序、折半插入排序、2-路插入排序、希尔排序
 */

/**
 * 直接插入排序
 * 直接插入排序的基本操作是将一个记录插入到已经排好的有序表中，从而得到一个新的、记录数增1的有序表
 *
 * 直接插入排序算法分析：
 * 有n个记录待排序，需进行2..n共n-1趟插入。
 * 
 * 第i趟插入完成的功能：
 * 在含有i-1个记录的有序序列r[1..i-1]中插入一个记录r[i]，插入后变成含有i个记录的有序序列r[1..i]
 */
function InsertSort($arr){
	$lenght = count($arr);
	if ($lenght<=1) {
		return $arr;
	}
	//从第$i=1个数开始循环
	for ($i=1; $i < $lenght; $i++) { 
		//设$x等于第$i个数的值
		$x = $arr[$i];
		//$j就是第0个数的位置
		$j = $i-1;
		//如果这个数的值小于前一个数，且前一个数大于等于0
		while ($x < $arr[$j] && $j>=0) {
			//那么就将这个数放到后面去
			$arr[$j+1] = $arr[$j];
			$j--;
		}
		$arr[$j+1] = $x;
	}
	return $arr;
}
echo "插入排序：";
echo implode(" ", InsertSort($arr))."<br/>";
